package 剑指II;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-28
 **/

public class Jz086分割回文子字符串 {

    /**
     * 给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
     * 回文串 是正着读和反着读都一样的字符串。
     * <p>
     * 示例 1：
     * 输入：s = "google"
     * 输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
     * 示例 2：
     * 输入：s = "aab"
     * 输出：[["a","a","b"],["aa","b"]]
     * 示例 3：
     * 输入：s = "a"
     * 输出：[["a"] 
     *  
     * 提示：
     * 1 <= s.length <= 16
     * s 仅由小写英文字母组成
     */

    private List<List<String>> result = new ArrayList<>();

    public String[][] partition(String s) {

        // 先用动态规划找出所有的回文子串
        boolean[][] dp = new boolean[s.length()][s.length()];

        // base
        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = true;
        }

        for (int i = dp.length - 1; i >= 0; i--) {

            for (int j = i + 1; j < dp.length; j++) {

                // 两个字符相等,则为回文子串
                if (j - i <= 2 && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                } else {
                    // 多个字符了,需要看左下角是否为回文子串
                    if (dp[i + 1][j - 1]) {
                        if (s.charAt(j) == s.charAt(i)) {
                            dp[i][j] = true;
                        }
                    }
                }

            }

        }

        this.dfs(s, 0, dp, new ArrayList<>());

        String[][] arr = new String[this.result.size()][];

        for (int i = 0; i < this.result.size(); i++) {
            arr[i] = new String[this.result.get(i).size()];
            for (int j = 0; j < this.result.get(i).size(); j++) {
                arr[i][j] = this.result.get(i).get(j);
            }
        }

        return arr;
    }

    private void dfs(String s, int index, boolean[][] dp, List<String> path) {

        if (index >= s.length()) {
            this.result.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < s.length(); i++) {
            if (dp[index][i]) {
                // 当前位置可以
                path.add(s.substring(index, i + 1));
                this.dfs(s, i + 1, dp, path);
                path.remove(path.size() - 1);
            }
        }

    }

    public static void main(String[] args) {
        Jz086分割回文子字符串 n = new Jz086分割回文子字符串();
        String[][] result = n.partition("google");
        System.out.println(JSON.toJSONString(result));
    }

}
